// Created by wxx on 2021/10/20 10:07
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：12 ms, 在所有 C++ 提交中击败了97.36%的用户
 * 内存消耗：13.7 MB, 在所有 C++ 提交中击败了93.69%的用户
 */
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>> &a) {

        sort(a.begin(), a.end());

        vector<vector<int>> res;
        int l = a[0][0], r = a[0][1];
        for (int i = 1; i < a.size(); i++) {
            if (a[i][0] > r) {  // 区间无交集
                res.push_back({l, r});
                l = a[i][0], r = a[i][1];
            } else r = max(r, a[i][1]);  // 区间有交集, 需要合并
        }
        res.push_back({l, r});  // 最后一个合并后的区间

        return res;
    }
};

void OutputBasicArray2D1(vector<vector<int>> nums) {

    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << "[";
        for (int j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ", ";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> intervals = {{1,  3},
                                     {2,  6},
                                     {8,  10},
                                     {15, 18}};
    OutputBasicArray2D1(Solution().merge(intervals));

    return 0;
}
